﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0160_SubarraySum : IAlgorithm
    {
        // 560. 和为 K 的子数组

        // 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

        // 提示：
        //  1 <= nums.length <= 2 * 10^4
        //  -1000 <= nums[i] <= 1000
        //  -10^7 <= k <= 10^7

        public void Test()
        {
            // 算法参数定义
            var nums = new int[] { -1, -1, 1 };
            // 算法执行与打印
            Console.WriteLine(SubarraySum(nums, 0));
        }

        // 算法
        // 输入：nums = [1,1,1], k = 2
        // 输出：2
        public int SubarraySum(int[] nums, int k)
        {
            int count = 0, pre = 0;
            var mp = new Dictionary<int, int>
            {
                { 0, 1 }
            };
            for (int i = 0; i < nums.Length; i++)
            {
                pre += nums[i];
                if (mp.ContainsKey(pre - k))
                    count += mp[pre - k];
                if(mp.ContainsKey(pre))
                    mp[pre]++;
                else
                    mp.Add(pre, 1);
            }
            return count;
        }
    }
}
